/**
 * Created with IntelliJ IDEA.
 * Description：
 * User：user
 * DATE:2021-10-23
 * Time:20:36
 */
class Node{
    public int val;//0
    public Node next;//null
    public Node(int val){
        this.val = val;
    }
}
public class MyLinkedList {

    public Node head;//单链表的头节点引用

    //穷举法创建链表
    public void createLinkedList(){
        Node node1 = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        Node node4 = new Node(4);
        this.head = node1;
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
    }

    //打印链表
    public void show(){
        Node cur = this.head;
        while(cur != null){
            System.out.print(cur.val + " ");
            cur = cur.next;
        }
        System.out.println();
    }

    //求链表的长度
    public int getSize(){
        Node cur = this.head;
        int count = 0;
        while(cur!=null){
            count++;
            cur = cur.next;
        }
        return count;
    }

    //头插法
    public void addFirst(int data){
        //当链表为空的时候仍然适用
        //插入一个结点的时候一定要记得先绑后面
        Node node = new Node(data);
        node.next = this.head;
        this.head = node;
    }
    // 尾插法
    public void addLast(int data){
        Node node = new Node(data);
        if(this.head == null){
            this.head = node;
            return;
        }
            Node cur = this.head;
            while(cur.next != null){
                cur = cur.next;
            }
            cur.next = node;
    }
    //任意位置插入,第一个数据节点为0号下标
    public boolean addIndex(int index,int data){
        Node node = new Node(data);
        if(index < 0 || index > this.getSize()){
            System.out.println("插入的位置不合法");
            return false;
        }
        if(index == 0){
            this.addFirst(data);
            return true;
        }
        if(index == this.getSize()){
            this.addLast(data);
            return true;
        }
        Node cur = this.findIndexSubOne(index);
        node.next = cur.next;
        cur.next = node;
        return true;
    }
    //查找某一下标结点的下一个结点
    private Node findIndexSubOne(int index){
        if(this.head == null){
            return null;
        }
        Node cur = this.head;
        while(index -  1 != 0){
            cur = cur.next;
            index--;
        }
        return cur;
    }
    //查找是否包含关键字key是否在单链表当中
    public boolean contains(int key){
        if(this.head == null){
            return false;
        }
        Node cur = this.head;
        //cur==null把整个链表走完了cur==null
        while(cur != null){
            if(cur.val == key){
                return true;
            }
            cur = cur.next;
        }
        return false;
    }
    private Node searchPrev(int key){
        Node cur = this.head;
        while(cur.next != null){
            if(cur.next.val == key){
                return cur;
            }
            cur = cur.next;
        }
        return  null;
    }
    //删除第一次出现关键字为key的节点
    public void remove(int key){
        if(this.head.val == key){
            this.head = this.head.next;
            return;
        }
        Node prev = this.searchPrev(key);
        if(prev == null){
            System.out.println("没有你要删除的结点");
            return;
        }
        Node del = prev.next;
        prev.next =  del.next;

    }
    //删除所有值为key的节点
    public void removeAllKey(int key){
        if(this.head == null){
            return;
        }
        Node prev = this.head;
        Node cur = this.head.next;
        while(cur != null){
            if(cur.val == key){
                prev.next = cur.next;
                //cur =cur.next;
            }else{
                prev = cur;
                //cur = cur.next;
            }
            cur = cur.next;
        }
        if(this.head.val == key){
            this.head = this.head.next;
        }
    }
    //清空链表
    public void clear(){
        this.head = null;//稍微粗暴
    }

}
